1494D - Dogeforces - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int p[N], v[N], ip[N];

int find(int x){
	if(x!=p[x]) return p[x]=find(p[x]);
	return x;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	#ifndef ONLINE_JUDGE	
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif

	int n; cin >> n;

	vector<array<int, 3>> q;

	for(int i = 0; i < n; i++){
		for(int l = 0; l < n; l++){
			int x; cin >> x;

			if(i == l) v[i] = x;
			else{
				q.push_back({x, i, l});
			}

		}
	}

	int cnt=n;


	sort(q.begin(), q.end());

	for(int i=0; i<1e5; i++) p[i]=i;

	for(int i=0; i<q.size(); i++){

		int val=q[i][0], x=q[i][1], y=q[i][2];
		x=find(x); y=find(y);

		if(v[x] >= val){
			p[y]=x;
			if(v[y]<val) ip[y]=x;
			continue;
		}
		else if(v[y]>=val){
			p[x]=p[y];
			if(v[x]<val) ip[x]=y;
			continue;
		}
		else if(v[y]<val&&v[x]<val){
			ip[x] = cnt;
			ip[y] = cnt;
			p[x] = p[y] = cnt;
			v[cnt] = val;
			p[cnt]=cnt;


			cnt++;
		}
	}

	cout<<cnt<<"\n";

	for(int i=0; i<cnt; i++) cout<<v[i]<<" ";

	cout<<"\n";

	cout<<cnt<<"\n";
	
	for(int i=0; i<cnt-1; i++)
	{
		cout<<i+1<<" "<<ip[i]+1<<"\n";
	}


}